Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:
0 < i, i + 1 < j, j + 1 < k < n - 1- The sum of subarrays
(0, i - 1),(i + 1, j - 1),(j + 1, k - 1)and(k + 1, n - 1)is equal.
(l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.
Example 1:
Input: nums = [1,2,1,2,1,2,1] Output: true Explanation: i = 1, j = 3, k = 5. sum(0, i - 1) = sum(0, 0) = 1 sum(i + 1, j - 1) = sum(2, 2) = 1 sum(j + 1, k - 1) = sum(4, 4) = 1 sum(k + 1, n - 1) = sum(6, 6) = 1
Example 2:
Input: nums = [1,2,1,2,1,2,1,2] Output: false
Constraints:
n == nums.length1 <= n <= 2000-106 <= nums[i] <= 106
Average Rating: 4.50 (12 votes)
Solution
Approach #1 Brute Force [Time Limit Exceeded]
Algorithm
Before we start looking at any of the approaches for solving this problem, firstly we need to look at the limits imposed on i, j and k by the given set of constraints. The figure below shows the maximum and minimum values that i, j and k can assume.
Thus, the limits based on the length of the array n can now be rewritten as:
1 ≤ i ≤ n-6
i+2 ≤ j ≤ n-4
j+2 ≤ k ≤ n-2
Having discussed the limits imposed on the cuts i, j, k that we will apply on the given array nums, let's look at the first solution that comes to our mind.
We simply traverse over all the elements of the array. We consider all the possible subarrays taking care of the constraints imposed on the cuts, and check if any such cuts exist which satisfy the given equal sum quadruples criteria.
Complexity Analysis
- Time complexity : O(n4). Four for loops inside each other each with a worst case run of length n.
- Space complexity : O(1). Constant Space required.
Approach #2 Cumulative Sum [Time Limit Exceeded]
Algorithm
In the brute force approach, we traversed over the subarrays for every triplet of cuts considered. Rather than doing this, we can save some calculation effort if we make use of a cumulative sum array sum, where sum[i] stores the cumulative sum of the array nums upto the ith element. Thus, now in order to find the sum(subarray(i:j)), we can simply use sum[j]−sum[i]. Rest of the process remains the same.
Complexity Analysis
-
Time complexity : O(n3). Three for loops are there, one within the other.
-
Space complexity : O(n). sum array of size n is used for storing cumulative sum.
Approach #3 Slightly Better Approach [Time Limit Exceeded]
Algorithm
We can improve the previous implementation to some extent if we stop checking for further quadruples if the first and second parts formed till now don't have equal sums. This idea is used in the current implementation.
Complexity Analysis
-
Time complexity : O(n3). Three loops are there.
-
Space complexity : O(n). sum array of size n is used for storing the cumulative sum.
Approach #4 Using HashMap [Time limit Exceeded]
Algorithm
In this approach, we create a data structure called map which is simply a HashMap, with data arranged in the format:
{csum(i):[i1,i2,i3,....]}, here csum(i) represents the cumulative sum in the given array nums upto the ith index and its corresponding value represents indices upto which cumulative sum=csum(i).
Once we create this map, the solutions gets simplified a lot. Consider only the first two cuts formed by i and j. Then, the cumulative sum upto the (j−1)th index will be given by: csum(j−1)=sum(part1)+nums[i]+sum(part2). Now, if we want the first two parts to have the same sum, the same cumulative sum can be rewritten as:
csum′(j−1)=csum(i−1)+nums[i]+csum(i−1)=2csum(i−1)+nums[i].
Thus, we traverse over the given array, changing the value of the index i forming the first cut, and look if the map formed initially contains a cumulative sum equal to csum′(j−1). If map contains such a cumulative sum, we consider every possible index j satisfying the given constraints and look for the equalities of the first cumulative sum with the third and the fourth parts.
Following the similar lines as the discussion above, the cumulative sum upto the third cut by kth index is given by
csum(k−1)=sum(part1)+nums[i]+sum(part2)+nums[j]+sum(part3).
For equality of sum, the condition becomes:
csum′(k−1)=3∗csum(i−1)+nums[i]+nums[j].
Similarly, the cumulative sum upto the last index becomes:
csum(end)=sum(part1)+nums[i]+sum(part2)+nums[j]+sum(part3)+nums[k]+sum(part4).
Again, for equality, the condition becomes:
csum′(end)=4∗csum(i−1)+nums[i]+nums[j]+nums[k].
For every cut chosen, we look if the required cumulative sum exists in map. Thus, we need not calculate sums again and again or traverse over the array for all the triplets (i,j,k) possible. Rather, now, we directly know, what cumulative sum to look for in the map, which reduces a lot of computations.
Complexity Analysis
-
Time complexity : O(n3). Three nested loops are there and every loop runs n times in the worst case. Consider the worstcase [0,0,0....,1,1,1,1,1,1,1].
-
Space complexity : O(n). HashMap size can go upto n.
Approach #5 Using Cumulative Sum and HashSet [Accepted]
Algorithm
In this approach, firstly we form a cumulative sum array sum, where sum[i] stores the cumulative sum of the array nums upto the ith index. Then, we start by traversing over the possible positions for the middle cut formed by j. For every j, firstly, we find all the left cut's positions, i, that lead to equalizing the sum of the first and the second part (i.e. sum[i−1]=sum[j−1]−sum[i]) and store such sums in the set (a new HashSet is formed for every j chosen). Thus, the presence of a sum in set implies that such a sum is possible for having equal sum of the first and second part for the current position of the middle cut(j).
Then, we go for the right cut and find the position of the right cut that leads to equal sum of the third and the fourth part (sum[n−1]−sum[k]=sum[k−1]−sum[j]), for the same middle cut as chosen earlier. We also, look if the same sum exists in the set. If so, such a triplet (i,j,k) exists which satisfies the required criteria, otherwise not.
Look at the animation below for a visual representation of the process:
Complexity Analysis
-
Time complexity : O(n2). One outer loop and two inner loops are used.
-
Space complexity : O(n). HashSet size can go upto n.
April 29, 2020 12:22 AM
Why I feel this should be a hard problem.
September 12, 2020 4:42 AM
Leetcode, please mark this question as hard before some half baked "smart" interviewer asks this in an interview to solve in 15 minutes.
August 31, 2020 7:52 AM
This should be marked as hard. Leetcode, pleaaaseeeeee curate the questions and tag appropriately.
Last Edit: November 30, 2020 2:15 AM
This solution is so smart. It just split two nested for loop and use the middle j to make sure that left for loop won't disrupt with the right half for loop. Two nested for loop is O(n^4) but once you split them, it's O(n^2)+O(n^2). I've solved hundreds of leetcode, but seldom did I meet such kind of solution using split nested for loop skills.
April 4, 2017 1:58 PM
Solution O(N^2)
def splitArray(self, nums):
n = len(nums)
s = [0] * (n + 1)
for i in range(n): s[i + 1] = s[i] + nums[i]
def check(l, r):
return set(s[m] - s[l] for m in range(l + 1, r + 1) if s[m] - s[l] == s[r + 1] - s[m + 1])
return any(check(0, j - 1) & check(j + 1, n - 1) for j in range(n))I find it's useful to write down the relations between prefix sum and target numbers to understand approach 5:
# [0...i-1], i, [i+1...j-1], j, [j+1...k-1], k, [k+1...n-1]
# [0...i-1] = s
# [0...j-1] = 2s + nums[i]
# [0...k-1] = 3s + nums[i] + nums[j]
# [0...n-1] = 4s + nums[i] + nums[j] + nums[k]
I believe the animation might be wrong? See the screenshot below:
sum[k-1] - sum[j] = 28 - 20 = 8
sum[n-1] - sum[k] = 36 - 30 = 6
8 != 6
April 25, 2017 1:59 AM
@aruballos Thanks for pointing it out. I have updated the animation. Please take a look.
April 15, 2017 8:54 PM
No, I think time complexity is O(n^2log(n)) , because set.add() will cost log(n)
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: bool splitArray(vector<int>& nums) { }};